package main

// 20. 有效的括号
func main() {

}

var StrMap = map[rune]rune{
	')': '(',
	']': '[',
	'}': '{',
}

func isValid(s string) bool {
	var stack []rune
	for _, ss := range s {
		if match, has := StrMap[ss]; has { // 要回退
			var lastOne rune
			if len(stack) == 0 {
				return false
			}
			stack, lastOne = stack[:len(stack)-1], stack[len(stack)-1]
			if match != lastOne {
				return false
			}
		} else {
			stack = append(stack, ss)
		}
	}
	return len(stack) == 0
}

// 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
//
//有效字符串需满足：
//
//左括号必须用相同类型的右括号闭合。
//左括号必须以正确的顺序闭合。
//每个右括号都有一个对应的相同类型的左括号。
//
//示例 1：
//
//输入：s = "()"
//
//输出：true
//
//示例 2：
//
//输入：s = "()[]{}"
//
//输出：true
//
//示例 3：
//
//输入：s = "(]"
//
//输出：false
//
//示例 4：
//
//输入：s = "([])"
//
//输出：true
//
//提示：
//
//1 <= s.length <= 104
//s 仅由括号 '()[]{}' 组成
